The invention relates to data packet scheduling in a communications system, and more particularly to efficient scheduling of best effort traffic with guaranteed latency traffic.
Many communications systems permit a data stream (“traffic”) to be associated with one of a number of quality of service levels, which define respective amounts of effort that the system will make with respect to the speed and accuracy of data transmission. One type of quality of service is called “best effort.” Best effort data streams, such as file-transfers or object-push (e.g., sending a business card, a photograph, etc.) do not require a guaranteed bandwidth or latency. Instead, bandwidth is permitted to vary in the course of the communication/transaction and data delivery latency is not of concern. The data transfer may even stall (temporarily) in favor of other activities.
Another type of quality of service is called “guaranteed (low) latency.” In contrast to best effort service, guaranteed (low) latency service is typically used for carrying an audio stream over a wireless (e.g., Bluetooth®) link while a video stream is simultaneously displayed. The audio stream must stay synchronized and be rendered with, at most, a small delay (typically less than 50 msec) relative to the rendering of the video stream.
When handling a guaranteed latency stream, the sending device guarantees a maximum amount of time in which a given (fixed) amount of data will be delivered (or discarded in case the transmission failed). Typically, these data transfers are repeated periodically, thus providing a constant bandwidth with a guaranteed maximum latency.
It is often the case that a same sending device will be responsible for several independent data streams at the same time, and these need not be associated with the same quality of service. When these independent data streams are to be time-wise multiplexed (i.e., meaning that they are not to be transmitted in parallel but instead are to take turns with transmissions), the sending device must utilize some sort of scheduling algorithm that will dictate which data stream's packets will be transmitted at any given time.
Scheduling algorithms must take into account the particular characteristics of the transmission protocol to be used. (A communication protocol is a set of rules that govern how data will be communicated from a sender to a receiver.) Here, communications equipment conforming to any of the standardized Bluetooth® protocols serves as a useful example. The Bluetooth® wireless interface, introduced by the Bluetooth Special Interest Group (Ericsson, Nokia, IBM, Toshiba and Intel) in 1998, is designed to be a low-cost, low-power and short-range cable replacement. A complete description of a Bluetooth® interface is far beyond the scope of this description. However, of relevance to the present discussion is how Bluetooth® provides for separate data streams to be communicated by a common sender.
Communication in a Bluetooth® system is packet-based, and links between Bluetooth® equipment are established on an ad hoc basis. In order to provide a mechanism for controlling the link, one of the units in the link is denoted as a master, and the other is denoted a slave. To enable more than one device to be linked together, one master may communicate with up to seven slaves in what is called a “piconet.” Packet exchange is based on the basic clock of the master, and all slaves are aware of any existing offset between the master's clock and their own so that they are able to know, at any time, what the master's clock would read. The air interface is time-wise divided up into sequentially occurring “slots” that progress in accordance with the “ticking” of the master's clock.
Further in accordance with Bluetooth® standards, transmission opportunities always take place in pairs, with a master transmitting first to one of the slaves (the master's transmissions include a slave address so that a slave can ascertain that it is the intended recipient of a transmission) followed by the slave having an opportunity to transmit back to the master. The master may operate in round-robin fashion, giving different slaves the opportunity to receive and then transmit a packet.
In the simplest case, a packet is sized so that it will exactly fit within the payload portion of one slot. (Header information is also communicated with the payload, whereby additional information such as the address of the intended recipient as well as acknowledgement information can also be transmitted.) When a 1-slot packet size is chosen, first the master is given an opportunity to transmit a packet to a slave in an even slot and this is immediately followed by that same slave being given an opportunity to transmit a packet back to the master in the next odd slot. An even slot and its immediately following odd slot are, when taken together, called a “slot pair.”
The Bluetooth® standards permit a variety of packet sizes to be used. In particular, packets may be 1, 3, or 5 slots long. (In practice, so-called “inter-packet guard spaces” are left between adjacent packets so that no one packet occupies the entirety of its allotted slot space.) Regardless of selected packet size, however, the master always begins its transmissions on an even slot, and slaves always begin their transmissions on an odd slot. This arrangement is illustrated in FIGS. 1a, 1b, and 1c. FIG. 1a illustrates a case involving only 1-slot packets. However, some aspects of the illustrated packets are the same regardless of packet size. For example, every packet includes an access code 101 (depicted in all instances by light gray shading) regardless of the packet's direction (master-to-slave or slave-to-master) or length. An access code 101 is used for synchronization, DC offset compensation and identification. Among other things, it is the mechanism by which a piconet can identify itself, and by which a page can be directed to a particular Bluetooth® device.
Every packet, regardless of direction or length also includes a header 103 (depicted in all instances by dark gray shading). The header 103, which is used for link control, includes a number of fields including a field that the sending device can encode to indicate either acknowledgement (“ACK”) or negative acknowledgement (“NACK”) of a last-received packet. In this respect, it is useful to note that the Bluetooth® protocol includes rules that call for the receiver of a packet to indicate ACK/NACK in its very next transmission opportunity. When a receiver signals “NACK” back to the sender of a packet, the sender can then decide whether to retransmit that same packet to the receiver rather than a new packet during its next transmission opportunity.
Packets also include payload portions. Unlike the access code and header portions 101, 103, the payload portion can be of varying length. FIG. 1a depicts examples in which all payloads are sized such that the entire packet length fits within one slot (so-called “1-slot packets”). Merely for purposes of illustration, six slots are illustrated, numbered consecutively “0” through “5”. As mentioned earlier, all master-to-slave packets are transmitted in even-numbered slots, and these are depicted throughout the figures by means of diagonal hatching in their payload portions. All slave-to-master packets are transmitted in odd-numbered slots, and these are depicted through the figures by means of horizontal hatching in their payload portions. (It will be understood that, in all instances, the accompanying access codes and headers of these payloads also travel in the same direction as their payloads.)
Accordingly, a first 1-slot packet having a payload 105 is communicated in slot 0. The next occurring slot (slot 1) is an odd-numbered slot, and therefore is used for communication of a 1-slot packet from slave-to-master. Slots 2 through 5 repeat this pattern, with even numbered slots being used for transmission of master-to-slave 1-slot packets, and odd numbered slots being used for transmission of slave-to-master packets.
FIG. 1b depicts an instance in which the master transmits a 3-slot packet starting in slot 0. It will be observed that the payload 109 of this packet extends from slot 0, through the entirety of slot 1, and into slot 2. Slot 3 is odd-numbered and therefore used for a slave-to-master packet transmission, and the same is true of slot 5. Slot 4 is even numbered, and in this instance illustrates a master's transmission of a 1-slot packet to the slave.
FIG. 1c depicts an instance in which the master transmits a 5-slot packet starting in slot 0. It will be observed that the payload 111 of this packet extends from slot 0, through the entireties of slots 1 through 2, and then into slot 4. The very next slot, slot 5, is odd-numbered and is therefore used for a slave-to-master packet transmission.
The term “transaction” is used herein to refer to the combined occurrence of a master-to-slave packet transmission (in an even-numbered slot) followed by the next-occurring slave-to-master packet transmission (in an odd-numbered slot). A so-called “frame” consists of two time-wise adjacent slots in which a transaction occurs (also called a “slot-pair”). The use of even/odd slot numbering to control the direction in which packets are communicated does not carry with it any implications regarding to what data stream packet transmissions belong except that the packets communicated in any given transaction (i.e., from master-to-slave followed by from slave-to-master) are both associated with a same data stream.
As used herein, the term “Bluetooth®-like” is used to indicate that the problems and solutions described herein are applicable not only to genuine Bluetooth® equipment, but more broadly to any communications equipment whose protocol follows a master/slave, odd/even slot, protocol such as was described above.
When independent data streams are to be time-wise multiplexed in accordance with a Bluetooth®-like protocol, the sending device must utilize some sort of scheduling algorithm that will dictate in which slots each data stream's transactions packets will begin. It is therefore useful to employ a prescheduling architecture, which is a scheduling architecture that pre-calculates/pre-schedules the different air activities some time in advance of the expected occurrence of those activities. Embodiments can be implemented in which pre-scheduling is separated from data path activities. This means that prescheduled frames of air-time may or may not actually be used for the allocated data transfers. The decision whether to actually use a given slot/frame for its pre-scheduled purpose can be made by, for example, a baseband controller that only operates in the prescheduled frames of air-time for that link.
Some embodiments that utilize a prescheduling architecture also employ an “overrule mechanism”, by which prescheduled activities for one link (e.g., planned transactions associated with data stream “A”) may be overruled by other activities that started in an earlier frame of air-time that was scheduled for another link (e.g., data stream “B”). Overruling a prescheduled activity only occurs if the preceding activity has not finished when the baseband controller is supposed to load the subsequent prescheduled frame. An activity's failure to finish when expected can occur, for example, if the amount of scheduled time is insufficient for the actual activity performed (e.g., if 1 or 2 frames are reserved for a data stream, but in actuality transmission of a 5-slot packet, which requires 3 frames, is started at the beginning of the first frame). A frame whose prescheduling is overruled is neither used for its prescheduled purpose, nor is this lost use compensated for in any way later on by, for example, allowing the overruled data stream to “steal back” a frame from the data stream that caused the overruling. Instead, the planned activity of the overruled data stream is effectively skipped by the baseband controller. This results in the overruled data stream's activities being delayed by some amount.
The scheduling of traffic with a low latency service type is usually prioritized over the scheduling of other traffic types and is very predictable with respect to data availability (from the source of the traffic). Intrinsically, low latency data streams have a high scheduling periodicity (i.e., short inter-packet timing) and often a relatively high duty cycle. This effectively leaves only limited time for the transmission of other traffic types. The problem is aggravated by the fact that a sender may need to retransmit any packet that is not acknowledged as having been successfully received at the target destination. Such retransmissions take up even more of the limited time that would otherwise be available for the transmission of other traffic types.
On the other hand, data availability of best effort data is not always predictable, making it more difficult for scheduling algorithms to mix best effort traffic with that having a guaranteed low latency service type. Transmissions for best effort traffic need to be fit efficiently into the limited air-time left over by the low latency data stream, maximizing the (re)transmission opportunities for best effort but also avoiding a pre-emption/overruling of subsequent transmissions of the low latency data stream. Otherwise, latency of the guaranteed traffic would not be guaranteed.
A timing diagram of a conventional prescheduling strategy for mixing low latency traffic with best effort traffic is depicted in FIG. 2a. Dotted lines are used here and in subsequent timing diagrams to illustrate the prescheduling of time frames, whereas solid lines are used here and in subsequent timing diagrams to denote the actual occurrence of a transaction. The conventional prescheduling strategy is characterized by the use of guard frames, such as the guard frames 201, 203 shown in FIG. 2a. A guard frame is a frame that has been deliberately left unallocated for use by any of the data streams. It is used to prevent one data stream's transaction (having a particular quality of service level) that has started in a preallocated time frame and that is continuing into successive time frames (i.e., by means of the “overrule” mechanism described above) from “spilling over” into a time frame that has been preallocated for use by another data stream having a different quality of service. The size of the guard space should be at least large enough to accommodate a remaining (“spillover”) part of an expected transaction. In the example of FIG. 2a as well as in all subsequent timing diagrams, crosshatching is used to indicate a low latency quality of service (of which guaranteed latency is one non-limiting example; as used throughout this disclosure including the claims, the term “low latency” should be understood to include but not be limited to guaranteed latency quality of service), and a solid white filling is used to indicate a best effort quality of service. Hence, it can be seen that the four time frames 205 are preallocated for use by a low latency (L.L.) data stream. These are followed by a guard space 201, which in turn is followed by seven time frames 207 that are preallocated for use by a best effort (B.E.) data stream. The seven time frames 207 preallocated for use by the best effort data stream are then followed by another guard space 203. In this example, the illustrated pattern is then repeated.
In this example, it is envisioned that each transaction (for both the low latency and best effort data streams) can occupy as many as three time frames. Hence, a last preallocated time frame for the low latency data stream should be followed by at least two unallocated time frames that serve as guard frames 201 (i.e., the one last preallocated time frame plus the following two unallocated time frames are together large enough to accommodate one transaction requiring three time frames.) Similarly, the last preallocated time frame for the best effort data stream should be followed by at least two unallocated time frames that serve as guard frames 203 for the best effort data stream.
FIG. 2b is a timing diagram illustrating an example in which all transactions complete successfully on the first try, making retransmissions unnecessary. A time frame 209 is preallocated for use by the best effort data stream, so consequently a best effort transaction 211 is started when the preallocated time frame is the current time frame. The transaction 211 is a payload carrying transaction that requires 3 time frames to perform. Consequently, the transaction started in time frame 209 spills over into the next two succeeding time frames. It is noted that the next two time frames following the time frame 209 have also been preallocated for use by the low latency data stream, so that none of the other (best effort) data stream's preallocated time frames have been overruled; however, this “spillover” would have occurred regardless.
Since, in this example, it is assumed that the transaction 211 has been completed successfully, there is no need for retransmission. The very next time frame 213 has also been preallocated for use by the low latency data stream and, thanks to the guard space 201, the baseband scheduler can safely begin another 3-frame transaction starting in the time frame 213. However, in this example it is assumed that there is no further data to transmit at this moment, so the time frame 213 is used only for a transaction 215 that can be completed within one time frame (e.g., polling and communicating an ACK/NAK to the slave). No transactions at all take place during the unallocated time frames of the guard space 201.
Following the first guard space 201, a time frame 217 has been preallocated for use by the best effort data stream. Consequently, a best effort transaction 219 begins when the preallocated time frame 217 is the current time frame, and extends into the next two time frames. The next time frame 221 is also allocated to a best effort data stream, so a three-frame best effort transaction 223 begins when the time frame 221 is the current time frame.
Following the transaction 223, the next time frame 225 is preallocated for use by best effort traffic, so yet another three-frame transaction 227 begins when the time frame 225 is the current time frame and extends into the next two time frames, which in this case is the second guard space 203.
The next preallocated time frame 229 is preallocated for use by low latency traffic, so a three-frame low latency transaction 231 begins when the time frame 229 is the current time frame, and extends into the next two time frames. Since it is assumed in this example that there are no retransmissions, the pattern described above is repeated for successive time frames.
It can be seen that, in the interest of ensuring the possibility of immediately providing an opportunity for a low latency retransmission, the guard spaces 101 are required. It can further be seen that this turns out to be wasted (unused) time when the retransmissions are not required. It would be desirable to make use of this air time for a best effort data stream.
FIG. 2c is an exemplary timing diagram illustrating time frame usage when single retransmissions are required in the low latency data stream. As before, a three-frame low latency transaction 233 begins when the time frame 209 is the current time frame. The transaction extends into the next two time frames, and here it is assumed that, at the conclusion of the transaction, the sender (master) receives acknowledgement information indicating that the packet was not successfully received by the receiver (slave). Consequently, the low latency sender uses its next preallocated time frame 213 to start a retransmission (“retry”) of the same transaction 235. This transaction 235 extends through the entirety of the first guard space 201.
The next time frame 217 is allocated for use by the best effort data stream, and as before, three best effort transactions 237, 239, 241 take place before the low latency data stream has another opportunity to start a transaction.
The low latency data stream's next opportunity to start a transaction is during time frame 229. In this example, this transaction 243 is assumed to be a new transaction. In theory, it could alternatively be a second retry of the transaction 233, if this had been needed after the first retry 235. However, in some embodiments the requirement for low- or guaranteed latency may require that no further retries are permitted due to timing requirements (i.e., it may be necessary, in order to satisfy quality of service requirements, to begin the next transaction and to abort the earlier failed transaction).
In this example, it is assumed that the transaction 243 was unsuccessful, so that the transaction is retried 245 beginning in time frame 247. Remaining illustrated transactions are performed in accordance with principles described and illustrated earlier.
FIG. 3a depicts another timing diagram of a conventional prescheduling strategy for mixing low latency traffic with best effort traffic. In this example, the preallocation is arranged to permit the low latency traffic as many as two retries (if needed) in the event of a failed initial transaction. As before, guard spaces 301, 303 are required to ensure, respectively, that the low latency transactions do not overrule the planned start of best effort transactions, and that best effort transactions do not overrule the planned start of low latency transactions. However, in order to ensure that the low latency data stream has two retry possibilities after each initial transaction, 7 successive (i.e., contiguous) time frames 305 are preallocated for use by the low latency data stream in each instance. In order to satisfy the low latency data stream's quality of service requirements, initial transaction opportunities cannot be spaced too far apart. Accordingly, in this example, time frames 307 preallocated for use by the best effort data stream have been reduced in number down to four successive time frames.
FIG. 3b is a timing diagram illustrating an example in which all transactions complete successfully on the first try, making retransmissions unnecessary. A time frame 309 has been preallocated for use by the low latency data stream, so when the time frame 309 is the current time frame, a three-frame low latency transaction 311 is started. In this example, the transaction 311 completes successfully, so that there is no need for a retry. Consequently, when the next scheduled time frame 313 is the current time frame, the sender (master) merely performs an action that can be completed within a single time frame. This leaves five time frames of wasted air time (i.e., three remaining time frames preallocated for use by the low latency data stream immediately followed by a two-frame guard space 301). It would certainly be beneficial to provide a way to utilize this air time for best effort traffic. In theory, the low latency sender could have started another three-frame transaction when time frame 313 is the current time frame. However, this is not depicted because it is often the case that low latency data is ready for transmission at known intervals, and the time frame 313 may be occurring too soon for a next low latency packet to be ready. Thus, there may simply be no low latency transaction that can be started at time frame 313.
Continuing with the example, a best effort transaction 317 is started when the time frame 319 (preallocated for use by best effort traffic) is the current time frame. The remainder of the example continues as described above.
FIG. 3c is an exemplary timing diagram illustrating time frame usage when one or two retransmissions are required in the low latency data stream. As before, a three-frame low latency transaction 321 begins when the time frame 309 is the current time frame. The transaction extends into the next two time frames, and here it is assumed that, at the conclusion of the transaction, the sender (master) receives acknowledgement information indicating that the packet was not successfully received by the receiver (slave). Consequently, the low latency sender uses its next preallocated time frame 313 to start a retransmission (“retry”) 323 of the same transaction. This transaction 323 extends through the next two time frames. In this example, it is assumed that the first retry is successful, making a second retry unnecessary. Consequently, during the next time frame 325 that has been preallocated for use by the low latency data stream, the sender (master) merely performs a transaction 327 that can be completed within a single time frame. This leaves the time frames associated with the first guard space 301 unused, and therefore wasted.
The next time frame 319 is allocated for use by the best effort data stream, and as before, two best effort transactions 329, 331 take place before the low latency data stream has another opportunity to start a transaction.
The low latency data stream's next opportunity to start a transaction is during time frame 333. In this example, this transaction 335 is assumed to be a new transaction, and it is further assumed that the transaction 335 was unsuccessful, so that the transaction is retried 337 beginning in time frame 339. This first retry transaction 337 is also assumed to be unsuccessful, so that the sender (master) performs as second retry transaction 341 beginning at the next opportunity, which is preallocated time frame 343. Remaining illustrated transactions are performed in accordance with principles described and illustrated earlier.
For at least the foregoing reasons, it is desirable to have methods and apparatuses that make better use of available air time when prescheduling a mix of low latency/guaranteed latency and best effort transactions in a Bluetooth®-like communications environment. It is further desirable to achieve this prescheduling goal without substantially (if at all) increasing the scheduler's processing load.